package cn.itcast.algorithm.sort.quicksort;

/**
 * 快排算法 - 三值区中法优化
 * create by zhangtian105 on 2021/6/15
 */
public class QuickSortThreeMid {

    public static void quickSortThreeMid(int waitArray[], int leftIdx, int rightIdx) {
        if (leftIdx < rightIdx) { // 指针未相遇，继续执行分治 将中间的这个数和第一个数交换
            // 获取枢纽值，并将其放在当前待处理序列末尾
            getMidIdx(waitArray, leftIdx, rightIdx) ;
            // 枢纽值被放在序列末尾
            int pivot = rightIdx - 1 ;

            // 左右指针
            int i = leftIdx, j = rightIdx - 1, targetV = waitArray[pivot] ;

            while (true) {
                while(waitArray[i] < targetV) {
                    i++ ;
                }

                while(j > leftIdx && waitArray[j] >= targetV) {
                    j-- ;
                }

                if (i < j) {
                    swapIdx(waitArray, i, j);
                }else {
                    break;
                }
            }

            if (i < rightIdx) {
                swapIdx(waitArray, i, rightIdx - 1);
            }

            quickSortThreeMid(waitArray, leftIdx, i - 1);
            quickSortThreeMid(waitArray, i + 1, rightIdx);
        }
    }

    /**
     * 处理枢纽值
     * @param waitArray
     * @param leftIdx
     * @param rightIdx
     */
    private static void getMidIdx(int[] waitArray, int leftIdx, int rightIdx) {
        int centerIdx = (leftIdx + rightIdx) / 2 ;

        // 一下交换取中间值
        if (waitArray[centerIdx] < waitArray[leftIdx]) {
            swapIdx(waitArray, leftIdx, centerIdx);
        }

        if (waitArray[rightIdx] < waitArray[leftIdx]) {
            swapIdx(waitArray, leftIdx, rightIdx);
        }

        if (waitArray[rightIdx] < waitArray[centerIdx]) {
            swapIdx(waitArray, centerIdx, rightIdx);
        }

        // 将枢纽元放置到right-1位置
        swapIdx(waitArray, centerIdx, rightIdx - 1);
    }

    /**
     * 交换值
     * @param waitArray
     * @param index1
     * @param index2
     */
    public static void swapIdx(int[] waitArray, int index1, int index2) {
        int tmp = waitArray[index1];
        waitArray[index1] = waitArray[index2];
        waitArray[index2] = tmp;
    }
}
